package com.zyk.grate_offer.class11;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangsan
 * @date 2021/5/30 20:05
 */
public class Code02_PalindromePartitioning {

    public static int minCut(String s) {
        char[] str = s.toCharArray();
        int N = str.length;
        boolean[][] map = createCheckMap(str);
        // [i ... N-1) 中尝试, 如果他是回文就等于 1 + dp[?]
        int[] dp = new int[N];
        dp[N - 1] = 1;
        for (int i = N - 2; i >= 0; i--) {
            if (map[i][N - 1]) {   // 剪枝
                dp[i] = 1;
            } else {
                int next = Integer.MAX_VALUE;
                for (int end = i; end < N; end++) {
                    if (map[i][end]) {
                        next = Math.min(next, dp[end + 1]);
                    }
                }
                dp[i] = next + 1;
            }
        }
        return dp[0] - 1;
    }

    // O(N²)
    // 生成了一个二位数组表含义. map[i][j], 代表从字符串i~j位置是否是回文串
    // i < j. i>j部分全为true
    public static boolean[][] createCheckMap(char[] str) {
        int N = str.length;
        boolean[][] dp = new boolean[N][N];
        /*for (int i = 0; i < N; i++) {
            dp[i][i] = true;    // i~i, 只有一个字符就是回文串
        }*/
        for (boolean[] arr : dp) {
            Arrays.fill(arr, true);
        }
        // 我是不是回文取决于, str[i] == str[j] && dp[i+1][j-1]是回文
        for (int i = N - 2; i >= 0; --i) {
            for (int j = i + 1; j < N; ++j) {
                dp[i][j] = str[i] == str[j] && dp[i + 1][j - 1];
            }
        }
        return dp;
    }

    // 切分字符, 使每个字符都是回文串
    // 返回所有的切分方法. 没有要求最少的切分
    public static List<List<String>> partition(String s) {
        char[] str = s.toCharArray();
        List<List<String>> res = new ArrayList<>();
        LinkedList<String> path = new LinkedList<>();
        boolean[][] map = createCheckMap(str);
        dfs(res, path, map, s, 0);
        return res;
    }

    public static void dfs(List<List<String>> res, LinkedList<String> path, boolean[][] map, String str, int i) {
        if (i == str.length()) {
            res.add(new ArrayList<>(path));
        } else {
            for (int end = 0; end < str.length(); end++) {
                if (map[i][end]) {
                    path.addLast(str.substring(i, end + 1));
                    dfs(res, path, map, str, i + 1);
                    path.removeLast();
                }
            }
        }
    }

    public static void main(String[] args) {
        String str = "aab";
        System.out.println(minCut(str));
    }

}
